#pragma once
#include<iostream>
using namespace std;

//二叉搜索树 K模型

template<class K>
struct BSTreeNode
{
	K _key;
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;

	BSTreeNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	//无参构造
	BSTree()
		:_root(nullptr)
	{}

	//插入
	bool Insert(const K& key)
	{
		//1、树为空，直接新增节点，赋值给root指针
	if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		//树不为空，按二叉搜索树性质查找插入位置，插入新节点
		Node* parent = nullptr;//记录插入节点的前一个指针，方便插入时操作
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;//插入已有的值返回false
			}
		}
		//找到位置，插入新节点
		cur = new Node(key);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}

	//查找
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

	//删除
	bool Erase(const K& key)
	{
		//首先查找元素是否在二叉搜索树上，如果不存在，则返回；
		Node* parent = nullptr;//当前节点的父亲
		Node* cur = _root;//找到当前的节点
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//相等找到
				//开始删除
				//0-1个孩子的情况
				if (cur->_left == nullptr)//要删除的节点的左为空 
				{
					//如果要删除的是没有左子树的 根节点，此时根节点是没有parent的 
					if (parent == nullptr)
					{
						_root = cur->_right;//直接让根节点指向右子树
					}
					else
					{
						//先判断我是父亲的左还是右
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;//让父亲指向我的右
						}
						else
						{
							//我是父亲的右
							parent->_right = cur->_right;
						}
					}
				
					delete cur;//删除节点
					return true;
				}
				else if (cur->_right==nullptr)//要删除的节点右为空
				{
					//如果要删除的是没有右子树的 根节点，此时根节点是没有parent的 
					if (parent == nullptr)
					{
						_root = cur->_left;//直接让根节点指向右子树
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}

					delete cur;//删除节点
					return true;
				}
				else
				{
					//2个孩子的情况
					//找要删除节点的右子树的最小节点作为替代节点  或者  找要删除节点的左子树的最大节点作为替代节点
					//找右子树的最小节点
					//Node* rightMinP = nullptr;//rightMinP为rightMin的父亲，方便删除rightMin节点
					Node* rightMinP = cur;//如果rightMinP为空，就不进入循环里面，就为空指针，所以直接指向cur
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinP = rightMin;
						rightMin = rightMin->_left;//一直往左找
					}
					cur->_key = rightMin->_key;//替代要删除的节点
					//rightMin不一定是rightMinP的左，也有可能是右（rightMinP = cur）
					if(rightMinP->_left == rightMin)
					    rightMinP->_left = rightMin->_right;
					else
						rightMinP->_right = rightMin->_right;

					delete rightMin;
					return true;
				}
			}
		}

		//没有找到
		return false;
		
	}

	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

private:
	Node* _root = nullptr;

};